package org.example.ch04;

import org.example.ch04.tree.ConstructTree;
import org.example.ch04.tree.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 *
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。

 */
public class isValidBST {

    public static void main(String[] args) {
        Integer[] array = new Integer[]{5,4,8,1,7,null,null};
        TreeNode treeNode = ConstructTree.constructTree(array);

//        boolean result= solution1(treeNode,Long.MIN_VALUE, Long.MAX_VALUE);
        boolean result = isValidBST(treeNode);
        System.out.println(result);
    }

    /**
     * node = 2 ,lower =1,upper = 3
     * @param node
     * @param lower
     * @param upper
     * @return
     */
    public static boolean solution1(TreeNode node, long lower, long upper){
        //递归的终结条件
        if(node == null){
            return true;
        }
        //执行本层逻辑
        if(node.getVal()<=lower || node.getVal()>=upper){
            return false;
        }

        //下探到下一层递归
        boolean left = solution1(node.left,lower,node.getVal());
        boolean right = solution1(node.right,node.getVal(),upper);
        //清理本层
        return left && right;
    }


    /**
     * 中序遍历
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
       Deque<TreeNode> stack = new LinkedList<TreeNode>();
       double lower = -Double.MAX_VALUE;
       while (!stack.isEmpty() && root!=null){
           while (root!=null){
               stack.push(root);
               root = root.left;
           }

           root = stack.pop();
           if(root.getVal()<=lower){
               return false;
           }
           lower = root.getVal();
           root = root.right;

       }
       return true;


    }


}
